class NodeVisitor:

    def __init__ (self):
        pass
          
    def visit (self,node,depth):
        if (node. val () <> None ):
            print " ( " + str (node. val ()) + " : " + str (node. color ()) + " : " + str (depth) + " ), " ,            
  


class RedBlackTree:

    red, black = range(2)
    def __copy(self,Node):
        self.__esquerdo = Node.__esquerdo
        self.__direito = Node.__direito
        self.__val = Node.__val
        self.__color = Node.__color

    def __RBinsertEsquerdo(self,val,sw):
        if (self.__esquerdo == None):
            self.__esquerdo = RedBlackTree(val)
        else:
            self.__esquerdo.__RBinsert(val,sw)

    def __RBinsertDireito(self,val,sw):
        if (self.__direito == None):
            self.__direito = RedBlackTree(val)
        else:
            self.__direito.__RBinsert(val,sw)

    def __rotEsq(self):
        if(self.__direito == None):
            return None
        me = RedBlackTree()
        me.__copy(self)
        x            = me.__direito
        me.__direito = x.__esquerdo
        x.__esquerdo = me
        return x

    def __rotDir(self):
        if (self.__esquerdo == None):
            return None
        me = RedBlackTree()
        me.__copy(self)
        x              = me.__esquerdo;
        me.__esquerdo  = x.__direito;
        x.__direito    = me;
        return x

    def __RBinsert(self,val,sw):
        esquerdo = self.__esquerdo
        direito  = self.__direito
        if ((esquerdo <> None) and (esquerdo.__color==RedBlackTree.red)and(direito <> None) and (direito.__color==RedBlackTree.red)):
            self.__color     = RedBlackTree.red
            esquerdo.__color = RedBlackTree.black
            direito.__color  = RedBlackTree.black
        if (val<self.__val):
            self.__RBinsertEsquerdo(val,0)
            esquerdo=self.__esquerdo
            if ((self.__color == RedBlackTree.red) and (esquerdo <> None) and (esquerdo.__color == RedBlackTree.red) and (sw == 1)):
                x = self.__rotDir()
                if (x <> None):
                    self.__copy(x)
            esquerdo = self.__esquerdo
            if (esquerdo <> None):
                ll = esquerdo.__esquerdo
                if (ll <> None):
                    if ((esquerdo.__color == RedBlackTree.red)and(ll.__color == RedBlackTree.red)):
                        x = self.__rotDir()
                        if (x <> None):
                            self.__copy(x)
                        self.__color = RedBlackTree.black
                        direito = self.__direito
                        if (direito <> None):
                            direito.__color = RedBlackTree.red
        else:
            self.__RBinsertDireito(val,1)
            direito = self.__direito
            if ((self.__color == RedBlackTree.red) and (direito <> None) and (direito.__color == RedBlackTree.red) and (sw == 0)):
                x = self.__rotEsq()        
                if (x <> None):
                    self.__copy(x)
                
            direito = self.__direito
            if (direito <> None):
                rr=direito.__direito
                if (rr <> None):
                    if((direito.__color == RedBlackTree.red)and(rr.__color == RedBlackTree.red)):
                        x = self.__rotEsq()
                        if (x <> None):
                            self.__copy(x)
                        self.__color = RedBlackTree.black
                        esquerdo = self.__esquerdo
                        if (esquerdo <> None):
                            esquerdo.__color = RedBlackTree.red


    def __init__(self,val=None):
        self.__esquerdo = None
        self.__direito = None
        self.__val = val
        self.__color = RedBlackTree.red
    
    def __str__ (self):
        return " [ " + str (self.__val) + " , " + str (self.__color) + " ] "

    def val (self):
        return self.__val

    def color (self):
        return self.__color

    def getEsquerdo(self):
        return self.__esquerdo
    
    def getDireito(self):
        return self.__direito
    
    def find (self,key):
        result = None
        if (key == self.__val):
            result = self
        elif (key < self.__val):
            if (self.__esquerdo  <> None ):
                result = self.__esquerdo. find(key)
        else :
            if (self.__direito <> None ):
                result = self.__direito. find(key)
        return result

    def inorderClass (self,visitor=NodeVisitor(),depth=0):
        if self.__esquerdo <> None :
            self.__esquerdo. inorderClass (visitor,depth + 1 )
        visitor. visit (self,depth)
        if self.__direito <> None :
            self.__direito. inorderClass (visitor,depth + 1 )
        
    def inorderFunction (self,visit,depth):
        if self.__esquerdo <> None :
            self.__esquerdo. inorderFunction (visit,depth + 1 )
        visit (self,depth)
        if self.__direito <> None :
            self.__direito. inorderFunction (visit,depth + 1 )
    def insert (self,val):
        self. __RBinsert (val, 0 );
        self.__color = RedBlackTree.black


